<?php

    /**
     * Sort
     *
     * Sorts a series of dependency pairs in linear order
     *
     * USAGE:
     *     $t      = new Core_Cron_Sort($dependencies);
     *     $sorted = $t->tsort();
     *
     * Where dependency_pairs is in the form: $name => (depends on) $value
     *
     * @package      Core
     * @subpackage   Cron
     *
     * @license      GNU Lesser General Public Licence see LICENCE-LGPL file or http://www.gnu.org/licenses/lgpl.html
     */
    class Core_Cron_Sort
    {

    ////////////////////////////////////////////////////////////////////////////
    //                                Variables                               //
    ////////////////////////////////////////////////////////////////////////////

        /**
         * Collection of nodes
         *
         * @var array
         */
        public $nodes = array();

    ////////////////////////////////////////////////////////////////////////////
    //                                 Methods                                //
    ////////////////////////////////////////////////////////////////////////////

        /**
         * Constructor
         *
         * @param       array       $dependencies
         * @param       boolean     $parse
         */
        public function __construct($dependencies = array(), $parse = false)
        {
            if ($parse === true) {
                $dependencies = $this->_parseDependencies($dependencies);
            }

            // Turn pairs into double-linked node tree
            foreach ($dependencies as $key => $dpair) {
                list($module, $dependency) = each($dpair);

                if (!isset($this->nodes[$module])) {
                    $this->nodes[$module] = new Core_Cron_Node($module);
                }

                if (!isset($this->nodes[$dependency])) {
                    $this->nodes[$dependency] = new Core_Cron_Node($dependency);
                }

                if (!in_array($dependency, $this->nodes[$module]->children)) {
                    $this->nodes[$module]->children[] = $dependency;
                }

                if (!in_array($module, $this->nodes[$dependency]->parents)) {
                    $this->nodes[$dependency]->parents[] = $module;
                }
            }
        }

        /**
         * Perform topological sort
         *
         * @param       array       $nodes : Optional array of node objects may be passed
         * @throws      Core_Exception
         * @return      array
         */
        public function tsort($nodes = array())
        {
            // Use this->nodes if it's populated and no param passed
            if (!@count($nodes) && count($this->nodes)) {
                $nodes = $this->nodes;
            }

            // Get nodes without parents
            $root_nodes = array_values($this->_getRootNodes($nodes));

            // Begin algorithm
            $sorted = array();

            while (count($nodes) > 0) {
                // Check for circular reference
                if (count($root_nodes) == 0) {
                    throw new Core_Exception('Fatal error: Circular reference found');
                }

                // Remove this node from root_nodes and add it to the output
                $n        = array_pop($root_nodes);
                $sorted[] = $n->name;

                // For each of its children, queue the new node finally and remove the original
                for ($i = (count($n->children) - 1); $i >= 0; $i--) {
                    $childnode = $n->children[$i];

                    // Remove the link from this node to its children ($nodes[$n->name]->children[$i])
                    // and remove the link from each child to this parent ($nodes[$childnode]->parents[?])
                    // then remove this child from this node
                    unset($nodes[$n->name]->children[$i]);

                    $parent_position = array_search($n->name, $nodes[$childnode]->parents);

                    unset($nodes[$childnode]->parents[$parent_position]);

                    // Check if this child has other parents, if not, add it to the root nodes list
                    if (!count($nodes[$childnode]->parents)) {
                        array_push($root_nodes, $nodes[$childnode]);
                    }
                }

                unset($nodes[$n->name]);
            }

            return $sorted;
        }

    ////////////////////////////////////////////////////////////////////////////
    //                            Protected Methods                           //
    ////////////////////////////////////////////////////////////////////////////

        /**
         * Returns a list of node objects that do not have parents
         *
         * @param       array       $nodes : Array of node objects
         * @return      array       Collection of node objects
         */
        protected function _getRootNodes($nodes)
        {
            $output = array();

            foreach ($nodes as $name => $node) {
                if (!count($node->parents)) {
                    $output[$name] = $node;
                }
            }

            return $output;
        }

        /**
         * Parses an array of dependencies into an array of dependency pairs
         *
         * The array of dependencies would be in the form:
         * $dependency_list = array(
         *     'name'  => array('dependency1', 'dependency2', 'dependency3'),
         *     'name2' => array('dependencyA', 'dependencyB', 'dependencyC'),
         *     ...etc
         * );
         *
         * @param       array       $dlist : Array of dependency pairs for use as parameter in tsort method
         * @return      array
         */
        protected function _parseDependencies($dlist = array())
        {
            $output = array();

            foreach ($dlist as $name => $dependencies) {
                foreach ($dependencies as $d) {
                    array_push($output, array($d => $name));
                }
            }

            return $output;
        }
    }